import unittest
from sets import Set
class Node():
    def __init__(self,data=None):
        self.data=data
        self.next=None
        
    def __str__(self):
        if self.next:
            return str(self.data)+','+self.next.__str__()
        return self.data and str(self.data) or ''
    def __repr__(self):
        return str(self.data)
        
        
        
    def append(self,data):
        newNode = Node(data)
        n =self
        while n.next!=None:
            n=n.next
        n.next=newNode
        
def deleteVal(head,val):
    if head.data==val:
        res=head.next
        head.next=None
        return res
    else:
        pre = head
        n=head.next
        while n:
            if n.data==val:
                pre.next=n.next
                return head
            pre=n
            n=n.next
        return head

def fromList(li):
    if li:
        head = Node(li[0])
        if len(li)>1:
            for i in li[1:]:
                head.append(i)
        return head
    return Node(None)

def removeDuplicates(li):
    "2.1"
    n=li
    while n:
        other=n.next
        pre=n
        while other:
            if other.data==n.data:
                pre.next=other.next
                other=other.next
            else:
                pre=other
                other=other.next
        n=n.next
    return li
        
        
class TestRemoveDuplicates(unittest.TestCase):
    inputs = ((fromList([1,2,2,3]),'1,2,3'),
              (fromList([1,2,2,2,2,2,3]),'1,2,3'),
              (fromList([1,2,3]),'1,2,3'),
              (fromList([1,2,2,2,2,2,3,3,3]),'1,2,3'),
              (fromList([3,3,3]),'3'),
              (fromList([1,1,1,3,3,3]),'1,3'),
              (fromList([]),''),
              
              )
    
    def testInputs(self):
        for in1,res in self.inputs:
            self.assertEqual(str(removeDuplicates(in1)),res)
            

def nthFromLast(li,nth):
    "2.2"
    if li==None or li.data==None:
        return None
    size=0
    n=li
    while n:
        n=n.next
        size+=1
    if nth>size:
        raise IndexError(str(nth)+' maior que o tamanho '+str(size))
    toGo = size-nth
    n=li
    for i in xrange(toGo):
        n=n.next
    return n.data

class TestNthFromLast(unittest.TestCase):
    inputs=(
            (fromList([1,2,3,4]),3,2),
            (fromList([1,2,3,4]),1,4),
            (fromList([1,2,3,4]),4,1),
            )
    def testInputs(self):
        for li,nth,res in self.inputs:
            self.assertEqual(nthFromLast(li, nth), res)
        
    def testRaise(self):
        self.assertRaises(IndexError, nthFromLast,fromList([1,2,3]),4)
        
        
def deleteNode(node):
    if node==None or node.next==None:
        return False
    node.data=node.next.data
    node.next=node.next.next
    return True
    
class TestDeleteNode(unittest.TestCase):
    def testDeleteMiddle(self):
        li = fromList([1,2,3,4,5])
        deleteNode(li.next.next)
        self.assertEqual(str(li), '1,2,4,5')
        
    def testDeleteFirst(self):
        li = fromList([1,2,3,4,5])
        deleteNode(li)
        self.assertEqual(str(li), '2,3,4,5')
    
    def testDeleteLast(self):
        li = fromList([1,2,3,4,5])
        self.assertFalse(deleteNode(li.next.next.next.next))
    
    def testDeleteEmpty(self):
        li = fromList([])
        deleteNode(li)
        self.assertEqual(str(li), '')    
        
        
def sumLists(a,b):
    "2.4"
    res = Node(None)
    plusOne = 0
    na = a
    nb = b
    while na or nb:
        sumDigit = (na!=None and na.data or 0)+(nb!=None and nb.data or 0)+plusOne
        plusOne = sumDigit/10
        sumDigit = sumDigit%10
        if res.data==None:
            res.data=sumDigit
        else:
            res.append(sumDigit)
        if na:
            na=na.next
        if nb:
            nb=nb.next
    if plusOne:
        res.append(plusOne)
    return res


class TestSumLists(unittest.TestCase):
    inputs = (
              (fromList([3,1,5]),fromList([5,9,2]),'8,0,8'),
              (fromList([1]),fromList([1]),'2'),
              (fromList([1]),fromList([9]),'0,1'),
              (fromList([3]),fromList([9,9]),'2,0,1'),
              )
    def testInputs(self):
        for a,b,res in self.inputs:
            self.assertEqual(str(sumLists(a, b)),res)
            
def findLoopStart(li):
    a=li
    dict = {}
    while a:
        if a in dict:
            return a
        dict[a]=1
        a=a.next
    return None

class TestFindLoopStart(unittest.TestCase):
    def testBasic(self):
        li = fromList([1,2,3,4])
        li.next.next.next.next=li.next
        self.assertEqual(findLoopStart(li).data, 2)
        
        li = fromList([1,2,3,4])
        li.next.next.next.next=li
        self.assertEqual(findLoopStart(li).data, 1)
        
        li = fromList([1,2,3,4,5])
        li.next.next.next.next=li.next.next.next
        self.assertEqual(findLoopStart(li).data, 4)
            

            
            
            

